
import com.sun.tools.javac.code.Attribute;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author huangxunhui
 * Date: Created in 18/10/18 上午9:40
 * Utils: Intellij Idea
 * Description: 存在重复元素
 */
public class ContainsDuplicate_217 {


    public boolean containsDuplicate(int[] nums) {

        //使用Set进行存储
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num))
                return true;
            set.add(num);
        }
        return false;
    }

    public boolean containsDuplicate1(int[] nums) {
        // 将数组先排序
        Arrays.sort(nums);
        for (int i = 1; i <nums.length ; i++) {
            if(nums[i] == nums[i-1]) return true;
        }
        return false;
    }

    public boolean containsDuplicate2(int[] nums) {
        // 将数组先排序
        for (int i = 1; i < nums.length ; i++) {
            for (int j = i-1; j >= 0 ; j--) {
                if (nums[i] > nums[j]) {
                    break;
                } else if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }


    public static void main(String[] args) {

        //TODO 需要优化
        int[] nums =  {3,1};

        int[] nums1 =  {1,2,3,4};

        int[] nums2 =  {1,1,1,3,3,4,3,2,4,2};

        ContainsDuplicate_217 containsDuplicate = new ContainsDuplicate_217();

//        long startTime = System.nanoTime();
//        System.out.println(containsDuplicate.containsDuplicate(nums));
//        System.out.println(containsDuplicate.containsDuplicate(nums1));
//        System.out.println(containsDuplicate.containsDuplicate(nums2));
//        long endTime = System.nanoTime();
//        System.out.println("SET 执行的时间： " + (endTime - startTime) / 1000000000.0);
//
//
//        long startTime1 = System.nanoTime();
//        System.out.println(containsDuplicate.containsDuplicate1(nums));
//        System.out.println(containsDuplicate.containsDuplicate1(nums1));
//        System.out.println(containsDuplicate.containsDuplicate1(nums2));
//        long endTime1 = System.nanoTime();
//        System.out.println("排序 执行的时间： " + (endTime1 - startTime1) / 1000000000.0);


        long startTime = System.nanoTime();
        System.out.println(containsDuplicate.containsDuplicate2(nums));
        System.out.println(containsDuplicate.containsDuplicate2(nums1));
        System.out.println(containsDuplicate.containsDuplicate2(nums2));
        long endTime = System.nanoTime();
//        System.out.println("执行的时间： " + (endTime - startTime) / 1000000000.0);

    }

}
